package com.awesome.javademo.algorithm.solution;


import com.awesome.javademo.algorithm.bean.ListNode;

/**
 * Author: JfangZ
 * Email: zhangjingfang@jeejio.com
 * Date: 2021/3/16 15:31
 * Description:
 */
public class SolutionLinkedList {
    // 删除链表中的节点
    /**
     * 题目:删除链表中的节点
     * 请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点head ，只能直接访问 要被删除的节点 。
     * 题目数据保证需要删除的节点 不是末尾节点 。
     * 输入：head = [4,5,1,9], node = 5
     * 输出：[4,1,9]
     * 解释：指定链表中值为5的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9
     */
    public static void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }

    // 删除链表的倒数第N个节点
    // 计算链表长度
    // 时间复杂的O(n)
    // 空间复杂的O(1)
    /**
     * 题目:删除链表的倒数第N个节点
     * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
     * 输入：head = [1,2,3,4,5], n = 2
     * 输出：[1,2,3,5]
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        // 增加伪头的新链表
        ListNode newHead = new ListNode(0,head);
        // 增加伪头的前驱链表
        ListNode pred = newHead;

        // 计算链表长度
        int length = 0;
        while(head!=null){
            head = head.next;
            length++;
        }
        // 找到前驱节点
        for (int i = 0; i < length - n; i++) {
            pred = pred.next;
        }
        // 删除操作
        pred.next = pred.next.next;
        // 去掉伪头
        return newHead.next;
    }


    // 翻转链表
    // 双指针迭代
    // 时间复杂的O(n)
    // 空间复杂的O(1)
    /**
     * 题目:反转链表
     * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
     * 输入：head = [1,2,3,4,5], n = 2
     * 输出：[1,2,3,5]
     * 解题过程
     * 1 2 3 4 5
     * 使用第三方媒介存储临时变量。
     * String temp = left
     * left = right
     * right = temp
     * --------------------
     * ListNode temp = cur.next
     * cur.next = pre
     * pre = cur
     * cur = temp
     */
    public static ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode prev = null;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }

    /**
     * 题目:合并两个有序链表
     * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     * 输入：l1 = [1,2,4], l2 = [1,3,4]
     * 输出：[1,1,2,3,4,4]
     * 输入：l1 = [], l2 = []
     * 输出：[]
     * 输入：l1 = [], l2 = [0]
     * 输出：[0]
     * 提示：
     * 两个链表的节点数目范围是 [0, 50]
     * -100 <= Node.val <= 100
     * l1 和 l2 均按 非递减顺序 排列
     */
//    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//
//    }

    /**
     * 题目:回文链表
     * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
     * 输入：head = [1,2,2,1]
     * 输出：true
     * 输入：head = [1,2]
     * 输出：false
     * 提示：
     * 链表中节点数目在范围[1, 105] 内
     * 0 <= Node.val <= 9
     */
//    public static boolean isPalindrome(ListNode head){
//
//    }

    // 快慢指针
    // 时间复杂的O(n)
    // 空间复杂的O(1)
    /**
     * 题目:环形链表
     * 给你一个链表的头节点 head ，判断链表中是否有环。
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
     * 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
     * 如果链表中存在环，则返回 true 。 否则，返回 false 。
     * 输入：head = [3,2,0,-4], pos = 1
     * 输出：true
     * 解释：链表中有一个环，其尾部连接到第二个节点。
     */
    public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) return false;
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }




}




